package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class No79 {
    public static void main(String[] args) {
//        char[][] b = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        char[][] b = {{'A','B','C','E'},{'S','F','E','S'},{'A','D','E','E'}};
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[i].length; j++) {
                System.out.print(b[i][j]+" ");
            }
            System.out.println();
        }
        String word = "ABCEFSADEESE";
        System.out.println(exist(b, word));
    }

    public static boolean exist(char[][] board, String word) {
        if(word.length()==1&&board[0][0]==word.charAt(0)) return true;
        boolean[][] value = new boolean[board.length][board[0].length];
        List<List<Character>> lists = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j]==word.charAt(0)){
                    backTrack(value,word,0,i,j,board,new ArrayList<>(),lists);
                }
                if(lists.size()>0) return true;
            }
        }
        return false;
    }

    public static void backTrack(boolean[][] value, String word, int index, int r, int c, char[][] board, List<Character> list,List<List<Character>> lists){
        if(index==word.length()){
            lists.add(list);
            return;
        }
        if(!value[r][c]&&board[r][c]==word.charAt(index)){
            if(r>=1){
                list.add(word.charAt(index));
                value[r][c]=true;
                backTrack(value,word,index+1,r-1,c,board,list,lists);
                value[r][c]=false;
                list.remove(list.size()-1);
            }
            if(r<board.length-1){
                list.add(word.charAt(index));
                value[r][c]=true;
                backTrack(value,word,index+1,r+1,c,board,list,lists);
                value[r][c]=false;
                list.remove(list.size()-1);
            }
            if(c>=1){
                list.add(word.charAt(index));
                value[r][c]=true;
                backTrack(value,word,index+1,r,c-1,board,list,lists);
                value[r][c]=false;
                list.remove(list.size()-1);
            }
            if(c<board[0].length-1){
                list.add(word.charAt(index));
                value[r][c]=true;
                backTrack(value,word,index+1,r,c+1,board,list,lists);
                value[r][c]=false;
                list.remove(list.size()-1);
            }
        }
    }
}
